package 二叉树高频题目_上_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code05_PreorderSerializeAndDeserialize {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    // 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
    // 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
    // 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
    // 比如如下两棵树
    //         __2
    //        /
    //       1
    //       和
    //       1__
    //          \
    //           2
    // 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
    public String serialize(TreeNode root) {
        StringBuilder strBuilder = new StringBuilder();
        fun(root, strBuilder);
        return strBuilder.toString();
    }

    public void fun(TreeNode root, StringBuilder stringBuilder){
        if(root == null){
            stringBuilder.append("#,");
        }else {
            stringBuilder.append(root.val + ",");
            fun(root.left, stringBuilder);
            fun(root.right, stringBuilder);
        }
    }

    public TreeNode deserialize(String data) {
        String[] str = data.split(",");
        cnt = 0;
        return fun2(str);
    }

    public static int cnt;

    public TreeNode fun2(String[] str){
        String cur = str[cnt++];
        if (cur.equals("#")) {
            return null;
        }else {
            TreeNode head = new TreeNode(Integer.valueOf(cur));
            head.left = fun2(str);
            head.right = fun2(str);
            return head;
        }
    }
}
